package myjava.i_collection;

/**
 * @Auther: cty
 * @Date: 2019/11/15 下午7:17
 * @Description: 自定义实现一个HashMap
 * @version: 1.0
 */
public class H_MyHashMap <K,V>{
    Node2[] table;  //位桶数组，bucket array
    int size;  //存放键值对的个数

    // 构造函数
    public H_MyHashMap(){
        table = new Node2[16];  //长度一般定义为2的整数幂
    }

    // 计算hash值
    public static int myHash(int hashCode,int length){

//        System.out.println("myHash: "+(hashCode%(length-1)));  //取模运算，效率低
//        System.out.println("myHash: "+(hashCode&(length-1)));  //位运算，效率高
        return hashCode&(length-1);
    }

    // 存放一个键值对
    public void put(K key,V value){

        Node2 newNode = new Node2();
        newNode.hash = myHash(key.hashCode(),table.length);
        newNode.key = key;
        newNode.value = value;
        newNode.next = null;

        Node2 temp = table[newNode.hash];
        Node2 iterlast = null;  //保存正在遍历的上一个节点
        boolean keyRepeat = false;

        if(temp==null){
            //数组此处元素为空，则直接将新节点放进去
            table[newNode.hash] = newNode;
            size++;
        }else {
            //数组此处元素不为空，则遍历对应链表
            while (temp!=null){

                if(temp.key.equals(key)){
                    //判断key如果重复，则覆盖
                    keyRepeat = true;  //标识为重复
                    temp.value = value;  //只是覆盖value即可
                    break;
                }else {
                    //key不重复，则遍历下一个
                    iterlast = temp;
                    temp = temp.next;
                }
            }

            if(!keyRepeat){  //未重复,则添加到列表最后
                iterlast.next = newNode;
                size++;
            }
        }
    }

    //根据key值获取value值
    public V get(K key){

        int hash = myHash(key.hashCode(),table.length);
        V value = null;

        if(table[hash]!=null){
            Node2 temp = table[hash];

            while (temp!=null){
                if(temp.key.equals((key))){
                    value = (V)temp.value;
                    break;
                }else {
                    temp = temp.next;
                }
            }
        }
        return value;
    }

    @Override
    public String toString() {

        StringBuffer sb = new StringBuffer("{");

        for(int i=0;i<table.length;i++){
            Node2 temp = table[i];
            while (temp!=null){
                sb.append(temp.key+":"+temp.value+",");
                temp = temp.next;
            }
        }
        sb.setCharAt(sb.length()-1,'}');
        return sb.toString();
    }

    public static void main(String[] args) {

        H_MyHashMap<Integer,String> m = new H_MyHashMap<>();
        m.put(10,"aa");
        m.put(20,"bb");
        m.put(30,"cc");
        m.put(20,"ssss");
        m.put(53,"gg");  //hash=5
        m.put(69,"hh");  //hash=5
        m.put(85,"kk");  //hash=5
        System.out.println(m);

        System.out.println(m.get(53));
        System.out.println(m.get(100));

    }
}


// 节点类
class Node2<K,V>{

    int hash;
    K key;
    V value;
    Node2 next;
}